package leetcode_800;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *CheapestFlightsWithinKStops_787 给定一个有向图 问A机场到B机场的最便宜机票是多少 而且不能转乘超过k
 *describe:典型深度优先遍历 AC 7%
 *2018年10月22日 下午1:26:01
 */
public class CheapestFlightsWithinKStops_787 {
	int min;
	int K;
	int dst;
	Map<Integer, Map<Integer, Integer>> map;
	boolean visited[];

	/**
	 * describe:典型深度优先搜索 记住要剪枝
	 * 2018年10月22日 下午12:42:16
	 */
	public int findCheapestPrice1(int n, int[][] flights, int src, int dst, int K) {
		this.min = Integer.MAX_VALUE;
		this.visited=new boolean[n];
		this.K = K;
		this.dst = dst;
		this.map = new HashMap<Integer, Map<Integer, Integer>>();
		for (int[] flight : flights) {
			Map<Integer, Integer> disMap = this.map.get(flight[0]);
			if (disMap == null) {
				disMap = new HashMap<Integer, Integer>();
			}
			disMap.put(flight[1], flight[2]);
			this.map.put(flight[0],disMap);
		}
		dfs(src, -1, 0);
		return this.min==Integer.MAX_VALUE?-1:this.min;
	}

	public void dfs(int now, int stop, int total) {
		if(visited[now])
			return ;
		if (now == dst)
			this.min = Math.min(this.min, total);
		// 否则不是目的地 那么stop要加1的 所以先判断是不超过了K
		if (stop == K||total>=this.min)//剪枝
			return;
		Map<Integer, Integer> disMap = this.map.get(now);
		if (disMap != null) {
			for (int next : disMap.keySet()) {// 遍历下一个机场
				visited[now]=true;
				dfs(next, stop + 1, total + disMap.get(next));
				visited[now]=false;//回溯
			}
		}
	}
}
